package com.lw.leetcode.back.b;

import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * 2044. 统计按位或能得到最大值的子集数目
 *
 * @author liw
 * @version 1.0
 * @date 2022/3/15 9:07
 */
public class CountMaxOrSubsets {

    public static void main(String[] args) {
        CountMaxOrSubsets test = new CountMaxOrSubsets();

        // 7
//        int[] arr =  {2,2,2};

        // 6
//        int[] arr =  {3,2,1,5};

        // 2
        int[] arr = {3, 1};

        int i = test.countMaxOrSubsets(arr);
        System.out.println(i);
    }


    private int[] nums;
    private int max;
    private int count;

    public int countMaxOrSubsets(int[] nums) {
        int item = 0;
        for (int num : nums) {
            item |= num;
        }
        this.max = item;
        this.nums = nums;
        int length = nums.length;
        Arrays.sort(nums);
        for (int i = length - 1; i >= 0; i--) {
            find(nums[i], i - 1);
        }
        return count;
    }

    private void find(int sum, int index) {
        if (sum == max) {
            if (index == -1) {
                count++;
            } else {
                count += (2 << (index));
            }
            return;
        }
        if (index < 0) {
            return;
        }
        find(sum | nums[index], index - 1);
        find(sum, index - 1);
    }

}
